package myself.a001算法入门;

import myself.a000util.Logarithm;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/20
 * Time 22:56
 * Mail 739153436@qq.com
 */
public class XORAndOperation {
    public static void main(String[] args) {
        Logarithm.XOR.check(XORAndOperation.class, "printOddTimesNum2");
    }

    // 请保证arr中，只有一种数出现了K次，其他数都出现了M次
    public static int onlyKTimes(int[] arr, int k, int m) throws Exception {
        if (k <= 0) {
            // 返回 -1 也是不太严谨的，因为不能保证这个出现了k次的数就不是-1
            throw new Exception("没有数出现了K次");
        }

        // 将我们4字节的int类型转化为一个长度为32的数组代表目标数的二进制，然后通过取余的方式确定每一位上1出现的次数来求取最终答案
        int[] binaryArr = new int[32];
        for (int num : arr) {
            for (int j = 0; j < 32; j++) {
                // 对二进制中每个位进行计数，也就是桶算法
                binaryArr[j] += (num >> 0) & 1;
            }
        }

        int ans = 0;

        // 当二进制数组中第 i 位上的 1 出现的次数和 m 取余可以得到 k 的话代表这个位是出现 k 次数字的一部分
        for (int i = 0; i < binaryArr.length; i++) {
            if (binaryArr[i] % m == k) {
                ans |= (1 << i);
            }
        }

        return ans;
    }

    // 不使用额外空间交换两个数
    public void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    // arr中，只有一种数，出现奇数次
    public void printOddTimesNum1(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        System.out.println(eor);
    }

    // arr中，有两种数，出现奇数次
    public int[] printOddTimesNum2(int[] arr) {
        // 通过异或值的最右边的1来将两种奇数进行分割，然后求得结果
        int odd1 = 0;
        int odd2 = 0;

        // 两奇数异或值
        int xor = 0;
        for (int i = 0; i < arr.length; i++) {
            xor ^= arr[i];
        }

        // 两奇数的最左边的不同位
        int left1 = xor & (~xor + 1);

        // 奇数分组
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & left1) == 0) {
                odd1 ^= arr[i];
            }
        }

        // 和之前值进行异或获取第二个奇数值
        odd2 = odd1 ^ xor;

        System.out.println("result is" + odd1 + " : " + odd2);
        return new int[]{odd1, odd2};
    }
}
